package org.getOffer.offer51;

/**
 * @Author: wjy
 * @Date: 2021/12/2 11:25
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] ints = {7, 5, 6, 4};
        System.out.println(solution.reversePairs(ints));

    }

    int count;
    public int reversePairs(int[] nums) {
        this.count = 0;
        merge2(nums, 0, nums.length - 1);
        return count;
    }

    public void merge(int[] nums, int left, int right) {
        int mid = (left + right) / 2;
        //int mid = left + ((right - left) >> 1);
        if (left < right) {
            merge(nums, left, mid);
            merge(nums, mid + 1, right);
            mergeSort(nums, left, mid, right);
        }
    }

    public void mergeSort(int[] nums, int left, int mid, int right) {
        int[] temparr = new int[right - left + 1];
        int index = 0;
        int temp1 = left, temp2 = mid + 1;

        while (temp1 <= mid && temp2 <= right) {
            if (nums[temp1] <= nums[temp2]) {
                temparr[index++] = nums[temp1++];
            } else {
                //用来统计逆序对的个数
                count += (mid - temp1 + 1);
                temparr[index++] = nums[temp2++];
            }
        }
        //把左边剩余的数移入数组
        while (temp1 <= mid) {
            temparr[index++] = nums[temp1++];
        }
        //把右边剩余的数移入数组
        while (temp2 <= right) {
            temparr[index++] = nums[temp2++];
        }
        //把新数组中的数覆盖nums数组
        for (int k = 0; k < temparr.length; k++) {
            nums[k + left] = temparr[k];
        }
    }

    public void merge2(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        this.merge2(nums, left, mid);
        this.merge2(nums, mid + 1, right);
        this.mergeSort2(nums, left, mid, right);
    }

    public void mergeSort2(int[] nums, int left, int mid, int right) {

        int temp1 = left;
        int temp2 = mid + 1;
        int[] arr = new int[right - left + 1];
        int index = 0;

        while (temp1 <= mid && temp2 <= right) {
            if (nums[temp1] <= nums[temp2]) {
                arr[index++] = nums[temp1++];
            } else {
                count += (mid - temp1) +1;
                arr[index++] = nums[temp2++];
            }
        }

        while (temp1 <= mid) {
            arr[index++] = nums[temp1++];
        }

        while (temp2 <= right) {
            arr[index++] = nums[temp2++];
        }

        for (int k = 0; k < arr.length; k++) {
            nums[k + left] = arr[k];
        }

    }

}
